1. Field of the Invention
The present invention relates to an encoder for encoding digital data composed of a plurality of bits, a method thereof, and a graphic processing apparatus.
2. Description of the Related Art
Computer graphics are often used in a variety of computer aided design (CAD) systems and amusement machines. Especially, along with the recent advances in image processing techniques, systems using three-dimensional computer graphics are becoming rapidly widespread.
In three-dimensional computer graphics, the color value of each pixel is calculated at the time of deciding the color of each corresponding pixel. Then, rendering is performed for writing the calculated value to an address of a display buffer (frame buffer) corresponding to the pixel.
One of the rendering methods is polygon rendering. In this method, a three-dimensional model is expressed as an composite of triangular unit graphics (polygons). By drawing the polygons as units, the colors of the pixels of the display screen are decided.
In polygon rendering, coordinates (x, y, z), color data (R, G, B, a), homogeneous coordinates (s, t) of texture data indicating a composite image pattern, and a value of the homogeneous term a for the respective vertexes of the triangle in a physical coordinate system are input and processing is performed for interpolation of these values inside the triangle.
Here, the homogeneous term a is, simply stated, like an expansion or reduction rate. Coordinates in a UV coordinate system of an actual texture buffer, namely, texture coordinate data (u, v), are comprised of the homogeneous coordinates (s, t) divided by the homogeneous term a to give "s/q" and "t/q" which in turn are multiplied by texture sizes USIZE and VSIZE, respectively.
In a three-dimensional computer graphic system using such polygon rendering, the texture data is read from the texture buffer when drawing, and texture mapping is performed for applying the read texture data on the surface of the three-dimensional model.
The texture mapped image data is written in a display memory (frame memory) after being subjected to predetermined processing.
The above three-dimensional computer graphic system, however, has a built-in first and second priority encoder (FSPE) for generating, for example, positional data of a first "1" bit and a second "1" bit seen from a most significant bit (MSB) in digital data comprised of a plurality of bits in a variety of circuits including for example a division circuit.
FIG. 10 is a view of the configuration of an FSPE encoder 50 of the related art.
As shown in FIG. 10, the FSPE encoder 50 comprises 16-bit priority encoders 51 and 53 and a 16-bit first valid bit mask unit 52.
In the FSPE encoder 50, input digital data 60 is input to the priority encoder 51 and the first valid bit mask unit 52.
In the priority encoder 51, a first "1" bit seen from the MSB in the digital data 60 is detected and 4-bit first bit encode data 61 indicating the position of the bit is generated.
In the first valid bit mask unit 52, first valid bit mask data 63, wherein a first "1" bit seen from the MSB in the digital data 60 is masked, that is, the bit is changed to "0", is generated and output to the priority encoder 53.
Next, in the priority encoder 53, a first "1" bit seen from the MSB in the first valid bit mask data 63 is detected and 4-bit second bit encode data 62 indicating the position of the bit is generated.
Below, the processing of each of the components of the FSPE encoder will be explained in detail with reference to a flow chart.
[Priority Encoder 51]
FIG. 11 is a flow chart of the processing in the priority encoder 51 in FIG. 10.
Step S1: "0.times.0f", that is, a hexadecimal "0f", is substituted for a variable "sft".
Step S2: The digital data 60 "in" is shifted toward a least significant bit (LSB) by exactly the amount of the variable "sft".
Step S3: It is judged whether or not the result of the shift at Step S2 is "1". When it is "1", the processing of Step S4 is carried out, while when it is not "1", the processing at Step S5 is carried out.
Step S4: The value "0.times.0f-sft" obtained by subtracting the variable "sft" from the "0.times.0f", that is, the hexadecimal "0f", is output as the first bit encode data 61.
Step S5: The variable "sft" is reduced by "1".
Step S6: It is judged whether or not the variable "sft" is 0 or more. When it is 0 or more, the processing of Step S2 is carried out, while when not, the processing of Step S7 is carried out.
Step S7: "0.times.00" is output as the first bit encode data 61.
Note that the processing shown in FIG. 11 is as shown in FIG. 12 when written in a C language.
The processing in the priority encoder 53 is the same as that in the above priority encoder 51 except that the processing is performed on the first valid bit mask data 63.
[First Valid Bit Mask Unit 52]
FIG. 13 is a flow chart of processing in the first valid bit mask unit 52 in FIG. 10.
Step S11: The value "0.times.0f", that is, the hexadecimal "0f", is substituted for the variable "sft".
Step S12: The digital data 60 "in" is shifted toward the LSB by exactly the amount of the variable "sft".
Step S13: It is judged whether or not the result of the shift at Step S12 is "1". When it is "1", the processing of Step S14 is carried out, while when it is not "1", the processing at Step S16 is carried out.
Step S14: The value "0.times.ff", that is, the hexadecimal "ff", is shifted toward the LSB by exactly "0.times.10-sft" obtained by subtracting the variable "sft" from "0.times.10". The result of the shift becomes a "mask".
Step S15: The digital data 60 "in" is shifted toward the LSB by exactly the amount of the "mask" obtained at Step S14. The result of the shift is output to the priority encoder 53 shown in FIG. 10 as the first valid bit mask data 63.
Step S16: The variable "sft" is reduced by "1".
Step S17: It is judged whether or not the variable "sft" is 0 or more. When it is 0 or more, the processing of Step S12 is carried out, while when not, the processing of Step S18 is carried out.
Step S18: The value "0.times.00" is output to the priority encoder 53 as the first valid bit mask data 63.
Note that the processing shown in FIG. 13 is as shown as FIG. 14 when written in a C language.
Summarizing the problem to be solved by the present invention, in the FSPE encoder 50 built in the above three-dimensional computer graphic system of the related art, as shown in FIG. 10, two 16-bit priority encoders 51 and 53 are necessary, so it suffers from a disadvantage that the apparatus becomes large in size.
Also, the path on which the first valid bit mask unit 52 and the priority encoder 53 for performing the 16-bit operation are placed becomes a critical path of the calculation processing time, therefore it suffers from a disadvantage that the processing time becomes long. There is also a disadvantage that the scale of the circuit becomes large.